/**
  @(#)$Id: AL_StackSeq.h 73 2013-10-10 12:38:11Z xiaoting $
  @brief     Stack (stack) in computer science is limited only in the end of the table to insert or delete operations linear form. 
  A stack is a data structure that in accordance with the principle of LIFO data storage, data is first pushed into the end of the 
  last data in the stack, you need to read the data when the data from the topmost pop. The stack is only one end of the inserted 
  and deleted special linear form. Buckets stacked items, first came under pressure in the heap, followed by a one to the heap. 
  Removed, only a one taken from above. Take the top of the heap and are carried at the bottom of the general is not moving. Stack 
  is a similar data structure barrels stacked items, delete and insert one end of said stack, said another pile bottom of the stack. 
  Insert commonly known as the push to delete is called the stack back. Also known as LIFO stack table.

  ////////////////////////////////Sequential storage structure//////////////////////////////////////////
  Using a set of addresses in the computer storage unit sequentially stores continuous linear form of individual data elements, called 
  the linear order of the table storage structure.

  Sequential storage structure is a type of a storage structure, the structure is the logically adjacent nodes stored in the physical 
  location of the adjacent memory cells, the logical relationship between nodes from the storage unit to reflect the adjacency. 
  Storage structure thus obtained is stored in order structure, usually by means of sequential storage structure computer programming 
  language (e.g., c / c) of the array to describe.

  The main advantage of the storage structure in order to save storage space, because the allocation to the data storage unit storing 
  all nodes with data (without regard to c / c language in the array size required for the case), the logical relationship between 
  the nodes does not take additional storage space. In this method, the node can be realized on a random access, that is, each node 
  corresponds to a number, the number can be calculated directly from the node out of the memory address. However, the main 
  disadvantage of sequential storage method is easy to modify the node insert, delete operations, may have to move a series of nodes.
          
  Benefits:
	Random Access table elements. 
  Disadvantages: 
    insert and delete operations need to move elements.

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-10 20:38:11 +0800 (周四, 10 十月 2013) $
  @Revision $Revision: 73 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_StackSeq.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_StackSeq.h 73 2013-10-10 12:38:11Z xiaoting $
 */

#ifndef CXX_AL_STACKSEQ_H
#define CXX_AL_STACKSEQ_H

///////////////////////////////////////////////////////////////////////////
//			AL_StackSeq
///////////////////////////////////////////////////////////////////////////

template<typename T> 
class AL_StackSeq
{
public:
	static const DWORD STACKSEQ_MAXSIZE				= 0xffffffff;
	static const DWORD STACKSEQ_DEFAULTSIZE			= 100;
	/**
	* Construction
	*
	* @param DWORD dwSize (default value: STACKSEQ_DEFAULTSIZE)
	* @return
	* @note
	* @attention
	*/
	AL_StackSeq(DWORD dwSize = STACKSEQ_DEFAULTSIZE);

	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	~AL_StackSeq();

	/**
	* IsEmpty
	*
	* @param	VOID
	* @return	BOOL
	* @note		Returns true stack is empty
	* @attention
	*/
	BOOL IsEmpty() const;

	/**
	* Pop
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Remove the top element and return data top element
	* @attention	if empty does not return a value... (please judge the stack is empty before use it)
	*/
	BOOL Pop(T& tTypeOut);

	/**
	* Push
	*
	* @param	const T& tData
	* @return	BOOL
	* @note		Add elements in the stack
	* @attention
	*/
	BOOL Push(const T& tData);

	/**
	* Size
	*
	* @param	VOID
	* @return	DWORD
	* @note		Returns the number of elements in the stack
	* @attention
	*/
	DWORD Size() const;
	
	/**
	* Top
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Back to the top element...
	* @attention	if empty does not return a value... (please judge the stack is empty before use it)
	*/
	BOOL Top(T& tTypeOut) const;

	/**
	* Clear
	*
	* @param	VOID
	* @return	VOID
	* @note		clear all data
	* @attention
	*/
	VOID Clear();
	
protected:
private:
	/**
	* GetBuffer
	*
	* @param VOID
	* @return VOID
	* @note get the work buffer
	* @attention when the buffer is not enough, it will become to double
	*/
	VOID GetBuffer();
	
	/**
	* IsFull
	*
	* @param VOID
	* @return BOOL
	* @note the buffer is full?
	* @attention
	*/
	BOOL IsFull() const;

	/**
	*Copy Construct
	*
	* @param const AL_StackSeq<T>& cAL_StackSeq
	* @return
	*/
	AL_StackSeq(const AL_StackSeq<T>& cAL_StackSeq);

	/**
	*Assignment
	*
	* @param const AL_StackSeq<T>& cAL_StackSeq
	* @return AL_StackSeq<T>&
	*/
	AL_StackSeq<T>& operator = (const AL_StackSeq<T>& cAL_StackSeq);

public:
protected:
private: 
	T*			m_pElements;
	DWORD		m_dwMaxSize;
	DWORD		m_dwSize;
};


/**
* Construction
*
* @param DWORD dwSize (default value: STACKSEQ_DEFAULTSIZE)
* @return
* @note
* @attention
*/
template<typename T> 
AL_StackSeq<T>::AL_StackSeq(DWORD dwSize):
m_pElements(NULL),
m_dwMaxSize(dwSize),
m_dwSize(0x00)
{
	if (0x00 == m_dwMaxSize) {
		//for memory deal
		m_dwMaxSize = 1;
	}
	GetBuffer();
}

/**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
template<typename T> 
AL_StackSeq<T>::~AL_StackSeq()
{
	if (NULL != m_pElements) {
		delete[] m_pElements;
		m_pElements = NULL;
	}
}

/**
* IsEmpty
*
* @param	VOID
* @return	BOOL
* @note		Returns true stack is empty
* @attention
*/
template<typename T> BOOL 
AL_StackSeq<T>::IsEmpty() const
{
	return (0x00 == m_dwSize) ? TRUE:FALSE;
}

/**
* Pop
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Remove the top element and return data top element
* @attention	if empty does not return a value... (please judge the stack is empty before use it)
*/
template<typename T> BOOL 
AL_StackSeq<T>::Pop(T& tTypeOut)
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}

	tTypeOut = m_pElements[Size()-1];
	//memset(&m_pElements[Size()-1], 0x00, sizeof(T));		//can not use memset, as to pointer or virtural pointer of class

	m_dwSize--;
	return TRUE;
}

/**
* Push
*
* @param	const T& tData
* @return	BOOL
* @note		Add elements in the stack
* @attention
*/
template<typename T> BOOL
AL_StackSeq<T>::Push(const T& tData)
{
	if (TRUE == IsFull()) {
		// full, need to get more work buffer
		GetBuffer();
	}
	m_pElements[Size()] = tData;
	
	m_dwSize++;
	return TRUE;
}

/**
* Size
*
* @param	VOID
* @return	DWORD
* @note		Returns the number of elements in the stack
* @attention
*/
template<typename T> DWORD 
AL_StackSeq<T>::Size() const
{
	return m_dwSize;
}

/**
* Top
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Back to the top element...
* @attention	if empty does not return a value... (please judge the stack is empty before use it)
*/
template<typename T> BOOL 
AL_StackSeq<T>::Top(T& tTypeOut) const
{
	if (TRUE == IsEmpty()) {
		//Empty
		return FALSE;
	}

	tTypeOut = m_pElements[Size()-1];
	return TRUE;
}

/**
* Clear
*
* @param	VOID
* @return	VOID
* @note		clear all data
* @attention
*/
template<typename T> VOID 
AL_StackSeq<T>::Clear()
{
	//memset(m_pElements, 0x00, sizeof(T)*Size());		//can not use memset, as to pointer or virtural pointer of class
	m_dwSize = 0x00;
}


/**
* GetBuffer
*
* @param VOID
* @return VOID
* @note get the work buffer
* @attention when the buffer is not enough, it will become to double
*/
template<typename T> VOID 
AL_StackSeq<T>::GetBuffer()
{

	if ( (FALSE == IsFull()) && (NULL != m_pElements) ) {
		//we do not need to get more buffer
		return;
	}

	if (NULL == m_pElements) {
		if(0 < m_dwMaxSize){
			//get the new work buffer
			m_pElements = new T[m_dwMaxSize];
			//memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);		//can not use memset, as to pointer or virtural pointer of class
		}
		return;
	}

	//we need to get more buffer, store the previous pointer
	T* pLastTpye = NULL;

	// it will become to double
	pLastTpye = m_pElements;
	if (STACKSEQ_MAXSIZE == m_dwMaxSize) {
		//can not get more buffer, please check the application
		return;
	}
	else if (STACKSEQ_MAXSIZE/2 < m_dwMaxSize) {
		m_dwMaxSize = STACKSEQ_MAXSIZE;
	}
	else {
		m_dwMaxSize *= 2;
	}
	if(0 < m_dwMaxSize){
		//get the new work buffer
		m_pElements = new T[m_dwMaxSize];
		//memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);		//can not use memset, as to pointer or virtural pointer of class
	}
	//need to copy the last to the current
	for (DWORD dwCpy=0x00; dwCpy<Size(); dwCpy++) {
		m_pElements[dwCpy] = pLastTpye[dwCpy];
	}
	//	memcpy(m_pElements, pLastTpye, sizeof(T)*Size());				//can not use memcopy, as to pointer

	//free the last work buffer
	delete[] pLastTpye;
	pLastTpye = NULL;
}

/**
* IsFull
*
* @param
* @return BOOL
* @note the buffer is full?
* @attention
*/
template<typename T> BOOL 
AL_StackSeq<T>::IsFull() const
{
	return (m_dwMaxSize <= Size()) ? TRUE:FALSE;
}

#endif // CXX_AL_STACKSEQ_H
/* EOF */
